package com.frank.code_notes.C01_array;

import cn.hutool.core.lang.Console;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 76. 最小覆盖子串
 * @Author zhoujr
 * @Data 2024/11/27 14:54
 */
public class L076MinCoveringSubstring {

    /**
     * @Description 使用滑窗算法解题，细节比较多，需要注意t中会有重复字符串、当have--之后会有非t中的字符
     */
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";

        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, have = 0, minLen = Integer.MAX_VALUE, minStart = 0;
        for (int right = 0; right < s.length(); right++) {
            char rightChar = s.charAt(right);
            if (tMap.containsKey(rightChar)) {
                map.put(s.charAt(right), map.getOrDefault(s.charAt(right), 0) + 1);
                // 小于等于t中字符数量，累加
                if (map.get(rightChar) <= tMap.get(rightChar)) {
                    have++;
                }
            }

            while (have == t.length()) {
                // 更新最小子串
                if (right - left < minLen) {
                    minLen = right - left;
                    minStart = left;
                }
                char leftChar = s.charAt(left);
                // 先处理干净非t中字符串
                if (tMap.containsKey(leftChar)) {
                    map.put(leftChar, map.get(leftChar) - 1);
                    // 累计数量小于t中字符数量
                    if (map.get(leftChar) < tMap.get(leftChar)) {
                        have--;
                    }
                }
                left++;
            }

        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen + 1);
    }


    public static void main(String[] args) {
        Console.log(minWindow("ADOBECODEBANC", "ABC"));
    }

}
